package 题目集.线段树or树状数组.树状数组;

import java.util.Scanner;

/**
 * https://www.luogu.com.cn/problem/P1637
 * 找出所有上升三元组的数量
 * 暴力思路：
 *      维护两个结构：
 *      1.每个数左侧 所有数作为一元组出现的次数
 *      2.每个数左侧 所有数作为二元组出现的次数
 *      每个位置作为上升三元组最后位置的方案数，就是结构2中，所有比它小的数的次数和。
 *      这两个结构需要支持单点添加，和区间求和。所以可以用树状数组维护。
 */
public class ch04_升序三元组 {

    static int n;
    static int maxN = (int) (3e4 + 10), maxA = (int) 1e5 + 1;
    static int[] tree1 = new int[maxA]; //记录一元组词频
    static int[] tree2 = new int[maxA]; //记录二元组词频

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        long res = 0;
        for (int i = 0; i < n; i++) {
            int v = sc.nextInt();
            add(tree1, v, 1);
            int level2 = range(tree1, 1, v - 1);
            if (level2 > 0) {  //v前面至少有一个（一元组）比他小的
                add(tree2, v, level2);
                res += range(tree2, 1, v - 1);    //前面有多少个比v小的二元组
            }
        }
        System.out.println(res);
    }

    public static void add(int[] tree, int i, int v) {
        while (i < tree.length) {
            tree[i] += v;
            i += lowbit(i);
        }
    }

    public static int range(int[] tree, int l, int r) {
        return sum(tree, r) - sum(tree, l - 1);
    }

    public static int sum(int[] tree, int i) {
        int res = 0;
        while (i > 0) {
            res += tree[i];
            i -= lowbit(i);
        }
        return res;
    }

    public static int lowbit(int x) {
        return x & -x;
    }
}
